ass Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
       vector<int> oddNum; 
       vector<int> evenNum;
       for(auto e:nums) 
       {
           if(e%2==0)
           {
               evenNum.push_back(e);
           }
           else
           {
               oddNum.push_back(e);
           }
       }
       vector<int> ret;
       auto itodd = oddNum.begin();
       auto iteven = evenNum.begin();
       int tmp=0;
       while(tmp<oddNum.size()+evenNum.size())
       {
           if(tmp%2==0)
           {
               ret.push_back(*iteven);
               iteven++;
           }
           else
           {
               ret.push_back(*itodd);
               itodd++;
           }
           tmp++;
       }
       return ret;
    }
};

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        vector<int> dp(array.size(),0);
        dp[0]=array[0];
        int max=dp[0];
        for(int i=1;i<array.size();i++)
        {
            dp[i]=std::max(dp[i-1]+array[i],array[i]);
            if(max<dp[i])
            {
                max=dp[i];
            }
        }
        return max;
    }
};
